package graph

import (
	"fmt"
)

func BFS(graph map[string][]string, startVertex string) {

	visited := make(map[string]bool)
	var queue []string

	vertexes := graph[startVertex]
	visited[startVertex] = true
	queue = append(queue, vertexes...)

	for {
		if len(queue) == 0 {
			break
		}
		e := queue[0]
		queue = queue[1:]
		if !visited[e] {
			fmt.Print(e)
		}
		visited[e] = true
		vs := graph[e]
		for _, v1 := range vs {
			if visited[v1] {
				continue
			}
			queue = append(queue, v1)
		}
	}

}

// 递归实现的话，还是使用ADT更加方便
func BFSv1(graph map[string][]string, s string) {

}

// 推荐使用对列的方式进行BFS
func BFSv2(graph map[string][]string, s string) {
	var q []string
	visited := make(map[string]bool)

	q = append(q, s)
	visited[s] = true
	for {
		if len(q) <= 0 {
			break
		}
		// pop
		vertex := q[0]
		q = q[1:]
		fmt.Println(vertex)
		neighbors := graph[vertex]
		for _, n := range neighbors {
			if !visited[n] {
				q = append(q, n)
				visited[n] = true
			}
		}

	}
}

// 递归实现bfs
